﻿//题目描述
//给定一个n个点、m条边的有向图，要求计算出点1到点n的最短距离。
//输入描述
//第一行：两个整数n, m。（1≤n≤10^3，1≤m≤10^5）
//接下来m行：每行三个整数
//𝑢𝑖,𝑤𝑖​，表示存在一条从ui​到𝑣𝑖​，权值为𝑤𝑖​的有向边。（1≤ui​, vi​≤n，1≤𝑤𝑖≤10^6）
//输出描述
//一个整数，表示点1到点n的最短距离；若不存在从点1到点n的路径，则输出−1。
//输入样例1
//3 3
//1 2 5
//2 3 2
//1 3 10
//输出样例1
//7
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+5;
 
struct Edge {
	int x, w;//x表示出点，w表示权值
};
vector <Edge>g[N];//用 邻接表 存储图，每个点 i 维护一个 vector<Edge>，存储 所有从 i 出发的边。
ll d[N],n,m;//用来存储从起点（点1）到每个点的最短距离。d[i] 表示从点1到点 i 的最短距离。
void dijkstra(int st) {
    memset(d, 0x3f, sizeof(ll) * (n + 1));  // 初始化距离数组
    d[st] = 0;  // 起点的距离为0
    bitset<N> vis;  // 用于标记节点是否已被访问
    for (int i = 1; i <= n; ++i) {
        // 找出最小距离点
        int u = 1;
        for (int j = 1; j <= n; ++j)
            if (vis[u] || (!vis[j] && d[j] < d[u])) u = j;
// vis[u]:这个条件检查节点 u 是否已经被访问过。如果 u 已经被访问过，则该条件为 true，
// 说明该节点已经处理过，因此不能再被选为下一个处理的节点。这个条件用于避免在处理过程中重复选择已经处理过的节点。
//vis[j] && d[j] < d[u]: 这个条件检查节点 j 是否未被访问过且它的距离 d[j] 是否小于当前节点 u 的距离 d[u]。
//它用于找到下一个最短路径的候选节点，确保选择距离最小且未访问的节点。
        vis[u] = true;  // 将节点 u 标记为已访问

        // 遍历与 u 相邻的节点
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i].x;   // 获取相邻节点 v
            int w = g[u][i].w;   // 获取边的权重 w
            if (!vis[v] && d[v] > d[u] + w) {
                d[v] = d[u] + w;  // 更新最短路径
            }
        }
    }
}
void solve() {
	 cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		if(u!=v)g[u].push_back({ v,w });//避免自环
	}
	dijkstra(1);//从1出发计算最短路径
	cout << d[n] << '\n';
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}